/*
 * hash表实现
 * 使用hashmap_init()创建，hashmap_add()添加，hashmap_del()删除，hashmap_find()查找，hashmap_destroy()销毁
 * 支持2种遍历方式，顺序为添加顺序
 * 1：hashmap_first_value()返回首个value, hashmap_first_value()获取下一个，当返回NULL时，表示已到末尾
 * 2: hashmap_walk()，需要提供自定义的walk回调
 * 支持rehash，当节点数 / 容量 > 比例因子时，进行再hash，仅在添加时检查，节点数减少时，不收缩容量
 * 多线程：不支持多线程，需要在调用api接口时，自己添加锁进行保护
 *
 * 具体实现：
 * 桶内节点有prev,next指针，头节点prev为NULL, 尾节点next为NULL, 插入时从头插入
 * 同时hash表记录全局节点列表，为此每个节点增加全局l_prev,l_next指针, 顺序为添加顺序，方便全局遍历
 *
 * Author: couryzh@aliyun.com
 * Date: 2023/03/28 16:48:53
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "hashmap.h"
#include "log.h"


/* 最小移位，对应最小容量prime[3] */
#define MIN_SHIFT 	3

/* 负荷因子 节点数/容量 */
#define LOAD_FACTOR 	0.45

struct hashentry {
    unsigned hash;      // 根据key计算出的hash值
    const void *key;
    void *value;
    // 所有本buck组成的双向循环列表 
    struct hashentry *next;
    struct hashentry *prev;

    // 全局列表的连接指针
    struct hashentry *l_next;
    struct hashentry *l_prev;
};

// 双向列表
struct hashlist {
    struct hashentry *head;
    struct hashentry *tail;
    struct hashentry *cursor;
};

/*
 * 对hash冲突，采用链表，所有需要提供hashmap_key_comp_func比较链表内的key
 */
struct hashmap {
    // bucket capacity
    unsigned int capacity;

    unsigned int entry_num;
    
    // key通过此方法计算hash位置
    hashmap_hash_func       key_func;
    // key比较方法
    hashmap_key_comp_func   comp_func;
    
    // 全局对象列表
    struct hashlist list;

    struct hashentry **buck;
};


// 再hash
int hashmap_rehash(hashmap_t *hp);


/*
 * 质数
 */
static const unsigned prime [] =
{
  1,          /* For 1 << 0 */
  2,
  3,
  7,
  13,
  31,
  61,
  127,
  251,
  509,
  1021,
  2039,
  4093,
  8191,
  16381,
  32749,
  65521,      /* For 1 << 16 */
  131071,
  262139,
  524287,
  1048573,
  2097143,
  4194301,
  8388593,
  16777213,
  33554393,
  67108859,
  134217689,
  268435399,
  536870909,
  1073741789,
  2147483647  /* For 1 << 31 */
};


static unsigned next_closest_size(unsigned curr_size)
{
    int i;
    unsigned next_size = curr_size * 2;

    for (i=0; i<sizeof(prime)/sizeof(prime[0]); i++) {
        if (prime[i] >= next_size)
            return prime[i];
    }
    // curr_size may be big enough, cannot grow
    return curr_size;
}



unsigned hashmap_default_string_key_func(const void *s)
{
    unsigned long h = 0, g;
    char *ps = (char *)s;

    while (*ps) {
        h = (h << 4) + *ps++;
        g = h & 0xf0000000L;
        if (g)
            h ^= (g >> 24);
        h &= ~g;
    }

    return h;
}

int hashmap_default_string_cmp_func(const void *a, const void *b)
{
    const char *as, *bs;
    as = (const char *)a;
    bs = (const char *)b;

    return strcmp(as, bs); 
}


hashmap_t *hashmap_init(hashmap_hash_func hash_func, hashmap_key_comp_func comp_func)
{
    struct hashmap *hp = NULL;

    hp = (struct hashmap *)calloc(1, sizeof(struct hashmap));
    if (!hp) {
        log_err("failed to alloc memory for hashmap\n");
        return NULL;
    }
    hp->capacity = prime[MIN_SHIFT];
    hp->buck = (struct hashentry **)calloc(hp->capacity, sizeof(struct hashentry *));
    if (!hp->buck) {
        log_err("failed to alloc memory for buck in hashmap\n");
        free(hp);
        return NULL;
    }
    hp->entry_num = 0;
    hp->key_func = hash_func == NULL ? hashmap_default_string_key_func : hash_func;
    hp->comp_func = comp_func == NULL ? hashmap_default_string_cmp_func : comp_func;
    hp->list.head = hp->list.tail = NULL;

    return hp;
}

// 计算桶序号
static unsigned hash_index(unsigned capacity, unsigned hash)
{
    return (hash * 11) % capacity;
}

// 计算桶序号，直接通过key_func函数
static unsigned hash_index_from_key(hashmap_t *hp, const void *key)
{
    return (hp->key_func(key) * 11) % hp->capacity;
}


int hashmap_rehash(hashmap_t *hp)
{
    unsigned idx, new_cap;
    struct hashentry **new_buck = NULL;
    struct hashentry *he = NULL, **head = NULL;

    if (hp->entry_num <= hp->capacity * LOAD_FACTOR)
        return 0;

    log_info("num entry: %u, capacity: %u\n", hp->entry_num, hp->capacity);
    new_cap = next_closest_size(hp->capacity);
    if (new_cap == hp->capacity) {
	log_warn("capacity %u cannot expand\n", hp->capacity);
	return 0;
    }
    new_buck = calloc(new_cap, sizeof(struct hashentry *));
    if (!new_buck) {
        log_err("failed to alloc new memory for buck in hashmap\n");
        return 0;
    }
#if 0
    unsigned i;
    struct hashentry *next_he = NULL;
    // 遍历旧buck，插入到新buck，不修改全局列表
    for (i=0; i<hp->capacity; i++) {
        for (he=hp->buck[i]; he; he=next_he) {
            next_he = he->next;
            idx = hash_index(new_cap, he->hash);
            head = &new_buck[idx];
            if (*head) {
                (*head)->prev = he;
            }
            he->next = *head;
            he->prev = NULL;
            *head = he;
        }
    }
#else
    // 通过全局列表遍历
    for (he=hp->list.head; he; he=he->l_next) {
        idx = hash_index(new_cap, he->hash);
        head = &new_buck[idx];
        if (*head) {
            (*head)->prev = he;
        }
        he->next = *head;
        he->prev = NULL;
        *head = he;
    }
#endif
    free(hp->buck);
    hp->buck = new_buck;
    hp->capacity = new_cap;

    return 1;
}



int hashmap_add(hashmap_t *hp, const void *key, void *value)
{
    unsigned idx = 0;
    struct hashentry *he = NULL, **head = NULL;

    he = (struct hashentry *)calloc(1, sizeof(struct hashentry));
    if (!he) {
        log_err("failed to alloc memory for hashmap_add\n");
        return 0;
    }
    he->hash = hp->key_func(key);
    idx = hash_index(hp->capacity, he->hash);
    hp->entry_num += 1;
    he->key = key;
    he->value = value;
    
    head = &hp->buck[idx];
    if (*head) {
        (*head)->prev = he;
    }
    he->next = *head;
    *head = he;

    // 串入全局列表
    if (!hp->list.head) {
        hp->list.head = hp->list.tail = he;
    }
    else {
        he->l_prev = hp->list.tail;
        hp->list.tail->l_next = he;
        hp->list.tail = he;
    }

    // 是否rehash
    hashmap_rehash(hp);

    return 1;
}


int hashmap_del(hashmap_t *hp, const void *key)
{
    unsigned idx = 0;
    struct hashentry *he = NULL;

    idx = hash_index_from_key(hp, key);
    for (he=hp->buck[idx]; he; he=he->next) {
        if (hp->comp_func(he->key, key) == 0) {
            if (he == hp->buck[idx]) {
                hp->buck[idx] = he->next;
            }
            if (he->prev)
                he->prev->next = he->next;
            if (he->next)
                he->next->prev = he->prev;

            // 从列表摘掉
            if (hp->list.head == he) {
                hp->list.head = he->l_next;
            }
            if (hp->list.tail == he) {
                hp->list.tail = he->l_prev;
            }

            if (he->l_next)
                he->l_next->l_prev = he->l_prev;

            if (he->l_prev)
                he->l_prev->l_next = he->l_next;

            free(he);
            hp->entry_num -= 1;
            return 1;
        }
    }

    return 0;
}

void *hashmap_find(hashmap_t *hp, const void *key)
{
    unsigned idx = 0;
    struct hashentry *he = NULL;

    idx = hash_index_from_key(hp, key);

    for (he=hp->buck[idx]; he; he=he->next) {
        if (hp->comp_func(he->key, key) == 0) {
            return he->value;
        }
    }
    return NULL;
}

void *hashmap_first_value(hashmap_t *hp)
{
    hp->list.cursor = hp->list.head;
    if (hp->list.cursor)
        return hp->list.cursor->value;
    else
        return NULL;
}

void *hashmap_next_value(hashmap_t *hp)
{
    void *value = NULL;
    if (!hp->list.cursor) return NULL;

    hp->list.cursor = hp->list.cursor->l_next;
    if (hp->list.cursor)
        value = hp->list.cursor->value;
    if (hp->list.cursor == hp->list.tail) {
        hp->list.cursor = NULL;
    }
    return value;
}


int hashmap_num_entry(hashmap_t *hp)
{
    return hp->entry_num;
}

void hashmap_walk(hashmap_t *hp, hash_walk_func func, void *priv)
{
    struct hashentry *he = NULL;

    for (he=hp->list.head; he; he=he->l_next) {
        func(he->key, he->value, priv);
    }
}

void hashmap_dump(hashmap_t *hp, hash_dump_entry_func func, void *priv)
{
    unsigned idx = 0;
    struct hashentry *he = NULL;

    printf("-------------------------------------------------\n");
    for (; idx<hp->capacity; idx++) {
        printf("[%4u] ", idx);
        for (he=hp->buck[idx]; he; he=he->next) {
            printf("  >%p: hash=%u, prev=%p, next=%p ", he, he->hash, he->prev, he->next);
            func(he->key, he->value, priv);
        }
        printf("\n");
    }
    printf("-------------------------------------------------\n");
}

int hashmap_destroy(hashmap_t *hp)
{
    unsigned idx = 0;
    struct hashentry *he = NULL, *next = NULL;

    for (; idx<hp->capacity; idx++) {
        for (he=hp->buck[idx]; he; he=next) {
            next = he->next;
            free(he);
        }
    }
    free(hp->buck);
    free(hp);

    return 1;
}

